﻿namespace 数独
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("模拟解数独! ");
            Sudoku sudoku = new Sudoku();
            while (true)
            {
                Console.WriteLine("\n准备开始:");
                Console.WriteLine("1. 继续执行");
                Console.WriteLine("其他: 结束程序");
                string choice = Console.ReadLine();
                if (!choice.Equals("1"))
                {
                    break;
                }
                Console.WriteLine("继续执行! ");

                char[][] board = new char[9][];
                for (int i = 0; i < 9; i++)
                {
                    Console.WriteLine($"请输入数独的第 {i + 1} 行(空白格用.代替)");
                    string[] s = Console.ReadLine().Split(' ');
                    char[] temp = new char[9];
                    for (int j = 0; j < 9; j++)
                    {
                        temp[j] = char.Parse(s[j]);
                    }
                    board[i] = temp;
                }
                Console.WriteLine("初始数独如下: \n");
                Console.WriteLine("   -----   -----   -----");
                for (int i = 0; i < 9; i++)
                {

                    string output = string.Join(' ', board[i]);
                    output += " |";
                    output = output.Insert(12, "| ");
                    output = output.Insert(6, "| ");
                    output = output.Insert(0, " | ");

                    Console.WriteLine(output);
                    if (i == 2 || i == 5 || i == 8)
                    {
                        Console.WriteLine("   -----   -----   -----");
                    }
                }

                TimeSpan startTime = DateTime.Now.TimeOfDay;
                Console.WriteLine("\n正在进行解题...\n");
                sudoku.SolveSudoku(board);
                TimeSpan endTime = DateTime.Now.TimeOfDay;

                Console.WriteLine("最终结果如下: \n");
                Console.WriteLine("   -----   -----   -----");
                for (int i = 0; i < 9; i++)
                {

                    string output = string.Join(' ', board[i]);
                    output += " |";
                    output = output.Insert(12, "| ");
                    output = output.Insert(6, "| ");
                    output = output.Insert(0, " | ");

                    Console.WriteLine(output);
                    if (i == 2 || i == 5 || i == 8)
                    {
                        Console.WriteLine("   -----   -----   -----");
                    }
                }
                TimeSpan timeSpan = endTime - startTime;
                Console.WriteLine($"\n解题花费时间 {timeSpan.Milliseconds} ms");
                /*
                    5 3 . . 7 . . . .
                    6 . . 1 9 5 . . .
                    . 9 8 . . . . 6 .
                    8 . . . 6 . . . 3
                    4 . . 8 . 3 . . 1
                    7 . . . 2 . . . 6
                    . 6 . . . . 2 8 .
                    . . . 4 1 9 . . 5
                    . . . . 8 . . 7 9
                */

            }


        }

        class Sudoku
        {
            public void SolveSudoku(char[][] board)
            {
                BacktrackSolveSudoku(board);
            }

            bool BacktrackSolveSudoku(char[][] board)
            {
                for (int i = 0; i < 9; i++)     // 遍历行
                {
                    for (int j = 0; j < 9; j++)     // 遍历列
                    {
                        // 跳过原始数字
                        if (board[i][j] != '.') continue;

                        // 逐个数字尝试放入
                        for (char val = '1'; val <= '9'; val++)
                        {
                            // 如果合适，放入
                            if (IsVaild(board, val, i, j))
                            {
                                board[i][j] = val;

                                // 如果找到合适一组，返回
                                if (BacktrackSolveSudoku(board)) return true;

                                // 回溯本次的放入操作
                                board[i][j] = '.';
                            }
                        }
                        // 9个数都试完了，都不行，那么就返回false
                        return false;
                        // 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
                        // 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
                    }
                }
                // 遍历完没有返回false，说明找到了合适棋盘位置了
                return true;
            }

            /// <summary>
            /// 判断放入数字是否合适
            /// </summary>
            /// <param name="board"></param>
            /// <param name="val"></param>
            /// <param name="row"></param>
            /// <param name="col"></param>
            /// <returns></returns>
            bool IsVaild(char[][] board, char val, int row, int col)
            {
                for (int i = 0; i < 9; i++)     // 判断同列是否重复
                {
                    if (board[i][col] == val) return false;
                }
                for (int i = 0; i < 9; i++)     // 判断同行是否重复
                {
                    if (board[row][i] == val) return false;
                }

                // 判断九宫格是否重复
                int startRow = (row / 3) * 3;
                int startCol = (col / 3) * 3;
                for (int i = startRow; i < startRow + 3; i++)
                {
                    for (int j = startCol; j < startCol + 3; j++)
                    {
                        if (board[i][j] == val) return false;
                    }
                }
                return true;
            }
        }
    }
}